package base.sort;

public class Qsort {

    /**
     * 快速排序（快排挖坑法）
     * @param arr
     * @param l
     * @param r
     */
    public static  void quickSort(int[] arr, int l, int r) {
        if( l >= r) return;
        int i = l, j = r;
        int pivot = l; // 初始坑位选择区间第一个值
        int key = arr[pivot];

        while (i<j) {
            while (i<j && arr[j]>=key)   j--; //先从右边往左找,找到比key小的
            arr[pivot] = arr[j]; //找到后放到坑位，j变成新的坑位
            pivot = j; //记录新的坑位

            while (i < j && arr[i]<=key) i++; //再从左往右找
            arr[pivot] = arr[i]; //找到后放到坑位，i变成新的坑位
            pivot = i;
        }
        pivot = i;
        arr[pivot] = key; //把最初的值放到最终的坑位

        quickSort(arr, l, pivot -1);
        quickSort(arr,pivot+1, r);
    }

    public static void main(String[] args) {
        int[] a = {2,3,50,33,-1,22,19};
        quickSort(a,0,a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }
}
